package demo1;
import java.util.Arrays;

/**
 * 错误解法-无法求得同以i下标元素为结尾时，多个相同长度的子序列*/
public class DynamicPlanningPractise {
    public int findNumberOfLIS(int[] nums) {
        /**
         正常求去求最长递增序列即可
         创建计数器

         状态表示：
         dp[i] 表示以i位置元素为结尾时 所有子序列中 最长递增子序列的长度
         状态转移方程：
         可以进行状态划分
         情况一：长度为1的子序列，此时子序列的长度为1
         情况二：长度大于1的子序列，此时需要先满足是递增序列 若是满足 再确定dp[i]的值，如下：
         if(nums[i]>nums[j]) dp[i] = Math.max(dp[i],dp[j]+1);
         初始化：
         由于所有元素最差情况下长度也可为1，故将dp表整体初始化为1
         返回值：
         创建一个二维计数器，后续详解*/
        int n = nums.length;
        int[][] count = new int[1][2]; //创建计数器，count[0][0]表示最长长度 count[0][1]表示该长度的数量
        //1 创建dp表
        int[] dp = new int[n];
        //2 初始化
        Arrays.fill(dp,1);
        //3 填表
        for(int i = 1; i < n; i++)
            for(int j = i-1; j >= 0; j--)
                if(nums[i]>nums[j]) {
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                    if(count[0][0]<dp[i]) {
                        count[0][0] = dp[i];
                    }
                    if(count[0][0]==dp[i]) count[0][1]+=1;
                }
        return count[0][1];
    }
    /**
     * 最长递增子序列的个数
     * 时间复杂度O（n*n）
     * 空间复杂度O（n）
     */
    public int findNumberOfLISOther(int[] nums) {
        /**
         状态表示：
         len[i]表示以i下标元素为结尾时，所有子序列中最长递增子序列的长度
         count[i]表示以i位置为结尾时，所有子序列中最长递增子序列的个数
         状态转移方程：
         len[i]可进行状态划分：
         情况一：长度为1的子序列，len[i]==1
         情况二：长度大于1的子序列，需要先满足是递增子序列，再求长度：
         len[i] = nums[i]>nums[j] ? Math.max(len[i],len[j]+1) : len[i];*/
        int n = nums.length;
        //1 创建dp表
        int[] len = new int[n];
        int[] count = new int[n];
        //2 初始化
        Arrays.fill(len,1);
        Arrays.fill(count,1);
        //3 填表
        for(int i = 1; i < n; i++) {
            for(int j = i-1; j >= 0; j--) {
                if(nums[i]>nums[j]) { //首先需要保证是递增序列
                    if(len[i]==len[j]+1) {
                        //之所以+=count[j],是因为len[j]+1==len[i]，
                        //那么所有以j下标元素为结尾并且长度为len[j]的子序列其加上nums[i]都能等于len[i]
                        //此即是count[i]的状态表示
                        count[i]+=count[j];
                    } else if(len[i]<len[j]+1) {
                        len[i] = len[j]+1;
                        //需要重置count计数器
                        count[i] = count[j];
                    }
                }
            }
        }
        //4 返回值
        int max = len[0];
        int ret = 1;
        for(int i = 1; i < n; i++) {
            if(max==len[i]) {
                ret+=count[i];
            } else if(max<len[i]) {
                max = len[i];
                ret = count[i];
            }
        }
        return ret;
    }

    /**
     * 求数组中最大值出现的次数*/
    public int function(int[] nums) {
        int maxValue = -0x3f3f3f3f;
        int count = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i]==maxValue) count++;
            else if(nums[i]>maxValue) {
                maxValue = nums[i];
                count = 1;
            }
        }
        return count;
    }
}
